import sys


class Solution:
    def nthUglyNumber(self, n: int) -> int:
        if n <= 0:
            return 0
        res = [1]
        p2, p3, p5 = 0, 0, 0

        for i in range(1, n):
            r2 = res[p2] * 2
            r3 = res[p3] * 3
            r5 = res[p5] * 5

            res.append(min(r2, r3, r5))

            if (res[i] == res[p2] * 2): p2 += 1
            if (res[i] == res[p3] * 3): p3 += 1
            if (res[i] == res[p5] * 5): p5 += 1

        return res[-1]


ans = Solution(  )
xx = ans.nthUglyNumber(10)
